package main
import "fmt"
/*
### 4.合并数组
* 给你两个按`非递减顺序`排列的整数数组nums1和nums2，另有两个整数m和n，
  分别表示nums1和nums2中的元素数目。
* 请你合并nums2到nums1中，使合并后的数组同样按`非递减顺序`排列。
* 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。
  为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
*链接：https://leetcode.cn/problems/merge-sorted-array
*/
func main() {
	num1 := []int{1,2,3,4,0,0,0}
	num2 := []int{2,5,6}
	merge(num1,4,num2,3)
}
	func merge(nums1 []int, m int, nums2 []int, n int) {
		// 初始化两个针，分别指向 nums1 和 nums2 的末尾
		p1 := m - 1
		p2 := n - 1
		// 初始化合并后的数组的末尾指针
		p := m + n - 1
		// 从后往前遍历，比较 nums1 和 nums2 的元素，并较大的元素入合并后的数组的末尾
		for p1 >= 0 && p2 >= 0 {
			if nums1[p1] > nums2[p2] {
				nums1[p] = nums1[p1]
				p1--
			} else {
				nums1[p] = nums2[p2]
				p2--
			}
			p--
		}
		// 如果 nums2 还有剩余元素，将其依次放入合并后的数组的前面
		for p2 >= 0 {
			nums1[p] = nums2[p2]
			p2--
			p--
		}
		fmt.Print(nums1)
	}

